/**
 * 合并区间
 * input [[1,3],[2,6],[8,10],[15,18]]
 * output [[1,6],[8,10],[15,18]]
 * 
 * [[1,4],[4,5]]
 * [[1,5]]
 * 
 * 思路
 *  合并的情况
 *      [1,4] [2,5]
 *  ===> [1,[2,4] 5]
 *  我们保证数组是"排序"的，即不会出现后面出现的元素区间会跑到前一个元素前面
 *  
 * 所以：
 *    1.排序  先以start排序，start均等的情况下再以end排序
 *        如 [2,6] [1,5] [3,4]
 *        ==> [1,5] [2,6] [3,4]  
 *    2. 排序之后的出现合并的情况
 * 
 *      即两个区间出现交集，取[前一个区间的start,后一个区间的end]
 *      当前区间与已确定区间的最后一个元素比较
 *      更新最后一个区间
 *    3.没有交集：
 *       后一个区间完全远离前一个区间
 *       则push  
 * 
 *     对了 定义的 Interval 函数其实就是对象 new 他！
 */
/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */
/**
 * @param {Interval[]} intervals
 * @return {Interval[]}
 */


var merge = function (intervals) {

    if (intervals && intervals.length > 0) {

        // 先排序
        // 如果start一致则按照end的升序排列
        // 否则按照start升排列
        let sorted = intervals.sort((a, b) => a.start === b.start ? a.end - b.end : a.start - b.start)

        let res = [sorted[0]];

        for (let i = 1; i < sorted.length; i++) {
            let
                temp = sorted[i],
                last = res[res.length - 1];

            // 存在合并区间的情况
            if (last.start <= temp.start && last.end >= temp.start && temp.end > last.end) {
                res[res.length - 1] = new Interval(last.start, temp.end);
            }
            // 直接push的情况
            else if (temp.start > last.end) {
                res.push(temp);
            }
        }
    }
    console.log(res);
    return res;
};


merge([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18]
]);